<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title> 归并排序 </title>
</head>
<body>
    <div><img src="./归并排序示意图.png" alt=""></div>
</body>
</html>
<script>
// 2021-06-07-夜-北京丰台-     
// 这个世界能够轻而易举，毫不费力做到的，只有贫穷和衰老，其他的都需要努力 
// 归并排序
/*
    排序一个数组 1先把数组从中间分成前后两部分 
                 2然后对前后两部分 分别排序 
                 3再将排好序的两部分合并到一起 
                  这样数组就都有序了 归并排序采用的是分治思想 
*/ 
const mergeSort = arr => {
	//采用自上而下的递归方法
	const len = arr.length;            //拿取length  去判断 
	if (len < 2) {                     //判断这个length 抛出
		return arr;
    }                                  // length >> 1 和 Math.floor(len / 2) 等价
	let middle = Math.floor(len / 2),  // 分为两份 向上取整 
		left = arr.slice(0, middle),   // slice(开始, 结束)
		right = arr.slice(middle);     // 拆分为两个子数组  分别截取左边的一份 和右边的一份
	return merge(mergeSort(left), mergeSort(right));
};

																												//俩函数套着 
const merge = (left, right) => {
   		const result = [];
		while (left.length && right.length) {
			if (left[0] <= right[0]) {     //注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
				result.push(left.shift()); //push入栈      shift删除数组的第一个元素 返回删除的元素
			} else {					   //pop 出栈
				result.push(right.shift());
			}
		}
		while (left.length) result.push(left.shift());
		while (right.length) result.push(right.shift());
		return result;                     //最后抛出
};
// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log('arr', mergeSort(arr));
// 2 3 4 5 15 19 26 27 36 ......	

// 第一，归并排序是原地排序算法吗 ？
// 这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。
// 实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了
// 在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
// 所以，归并排序不是原地排序算法。


// 第二，归并排序是稳定的排序算法吗 ？
// merge 方法里面的 left[0] <= right[0] ，保证了值相同的元素，在合并前后的先后顺序不变。归并排序是一种稳定的排序方法。

// 第三，归并排序的时间复杂度是多少 ？
// 从效率上看，归并排序可算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步, 又每步都是一个普通的合并子数组的过程，时间复杂度为 O(n)，故其综合时间复杂度为 O(nlogn)。
// 最佳情况：T(n) = O(nlogn)。
// 最差情况：T(n) = O(nlogn)。
// 平均情况：T(n) = O(nlogn)。


background-image: url('')


</script>